// 递归
// 本质是：解决主问题时，发现相同子问题，解决主问题和子问题的方法相同 (主问题有可能就是子问题)
// 心理暗示：宏观看待递归问题，把递归函数当成黑盒，相信这个黑盒一定能完成任务
// 技巧：
//      找到重复子问题 -> 设计函数头
//      子问题是如何解决的 -> 函数体的书写
//      注意递归函数的出口 -> 关注问题不能分割的情况
// 拓展：如果一个题目可以用决策树画出来，那么也可以通过递归解决
// 二叉搜索树要用中序遍历去做

// 例题 4：
// 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
//
//        有效 二叉搜索树定义如下：
//
//        节点的左子树只包含 小于 当前节点的数。
//        节点的右子树只包含 大于 当前节点的数。
//        所有左子树和右子树自身必须也是二叉搜索树。
//
//
//        示例 1：
//
//
//        输入：root = [2,1,3]
//        输出：true
//        示例 2：
//
//
//        输入：root = [5,1,4,null,null,3,6]
//        输出：false
//        解释：根节点的值是 5 ，但是右子节点的值是 4 。
//
//
//        提示：
//
//        树中节点数目范围在[1, 104] 内
//        -231 <= Node.val <= 231 - 1

// 解题思路：
// 二叉搜索树的中序遍历结果是一个有序数组
// 利用上述性质进行判断

public class IsValidBST {
    long prev = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if(root == null) return true;
        boolean left = isValidBST(root.left);
        if(!left) return false;
        if(prev >= root.val) return false;
        prev = root.val;
        boolean right = isValidBST(root.right);
        return right;
    }
}
